package array;

import java.util.Arrays;

public class Permutation {
    public static void main(String[] args) {
        int n = 12;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = i + 1;
        System.out.println(Arrays.toString(a));
        boolean isLastPermutation;
        long start = System.currentTimeMillis();
        do {
            isLastPermutation = generateNextPerm(a);
           // System.out.println(Arrays.toString(a));
        } while (!isLastPermutation);
        long end = System.currentTimeMillis();
        System.out.println(n+":  "+(end-start));

    }

    private static boolean generateNextPerm(int[] a) {
        if (a == null || a.length < 2) return true;
        int i=-1;
        for(int k=a.length-2; k>=0; k--){
            if(a[k]<a[k+1]){
                i=k;
                break;
            }
        }
        if(i==-1) return true;

        int j=a.length-1;
        while(a[j]<a[i]) j--;
        swap(a,i,j);
        reverse(a,i+1,a.length-1);
        return false;
    }

    private static void reverse(int[] a, int left, int right) {
        for(int i=left; i<= left + (right-left)/2; i++) swap(a,i, left+right - i);
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
